# Copyright 2007 Boris Dusek
#
# This file is part of grapy.
#
# Grapy is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, version 3 of the License.
#
# Grapy is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Grapy.  If not, see <http://www.gnu.org/licenses/>.

from grapy.DFSHooks import DFSHooks,CoreDFSHooks

class TopologicalSortDFSHooks(DFSHooks):

    dep=[CoreDFSHooks]

    @staticmethod
    def dfs_main_begin(environ):
        environ.is_acyclic = True
        environ.topological_order = []
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_end(environ,u):
        environ.topological_order.insert(0,u)
        return DFSHooks.HOOK_OK

    @staticmethod
    def dfs_visit_back_edge(environ,u,v):
        environ.is_acyclic = False
        raise NotImplementedError("Topological sort works only for acyclic \
graphs, encountered back edge (%s,%s)" % (u,v))


def topological_order(g,dfs_environ=None):
    topological_order = []
    if not dfs_environ:
        dfs_hooks = DFSHooksSuite([TopologicalSortDFSHooks])
        dfs_hooks.resolve_deps()
        dfs_environ = g.DFS(dfs_hooks)
        topological_order = dfs_environ.topological_order
    else:
        topological_order = [item[0] for item in \
                reversed(sorted([reversed(it) for it in \
                        dfs_environ.f.iteritems()]))]
    return topological_order

